0526. 优美的排列【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 回溯

1. 📝 题目描述

• leetcode

假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始），只要满足下述条件 之一，该数组就是一个 优美的排列 ：

• perm[i] 能够被 i 整除
• i 能够被 perm[i] 整除

给你一个整数 n，返回可以构造的 优美排列 的 数量。

---

示例 1：

输入：n = 2
输出：2
解释：
第 1 个优美的排列是 [1,2]：
    - perm[1] = 1 能被 i = 1 整除
    - perm[2] = 2 能被 i = 2 整除
第 2 个优美的排列是 [2,1]:
    - perm[1] = 2 能被 i = 1 整除
    - i = 2 能被 perm[2] = 1 整除

示例 2：

输入：n = 1
输出：1

---

提示：

• 1 <= n <= 15

2. 🎯 s.1 - 回溯

c

int count;
bool visited[16];

void dfs(int n, int pos) {
    if (pos > n) { count++; return; }
    for (int i = 1; i <= n; i++) {
        if (!visited[i] && (i % pos == 0 || pos % i == 0)) {
            visited[i] = true;
            dfs(n, pos + 1);
            visited[i] = false;
        }
    }
}

int countArrangement(int n) {
    count = 0;
    memset(visited, false, sizeof(visited));
    dfs(n, 1);
    return count;
}

js

/**
 * @param {number} n
 * @return {number}
 */
var countArrangement = function (n) {
  let count = 0
  const visited = new Array(n + 1).fill(false)
  const dfs = (pos) => {
    if (pos > n) {
      count++
      return
    }
    for (let i = 1; i <= n; i++) {
      if (!visited[i] && (i % pos === 0 || pos % i === 0)) {
        visited[i] = true
        dfs(pos + 1)
        visited[i] = false
      }
    }
  }
  dfs(1)
  return count
}

py

class Solution:
    def countArrangement(self, n: int) -> int:
        self.count = 0
        visited = [False] * (n + 1)
        def dfs(pos):
            if pos > n:
                self.count += 1
                return
            for i in range(1, n + 1):
                if not visited[i] and (i % pos == 0 or pos % i == 0):
                    visited[i] = True
                    dfs(pos + 1)
                    visited[i] = False
        dfs(1)
        return self.count

• 时间复杂度：$O(k)$，$k$ 为满足条件的排列数
• 空间复杂度：$O(n)$

算法思路：

• 从位置 1 开始回溯，尝试将每个未使用的数放在当前位置
• 只有当 i % pos == 0 或 pos % i == 0 时才放置
• 统计所有合法排列数